Search Results

Documents authored by Kushilevitz, Eyal

Document
DOI: 10.4230/LIPIcs.ITCS.2017.7
Low-Complexity Cryptographic Hash Functions

Authors: Benny Applebaum, Naama Haramaty-Krasne, Yuval Ishai, Eyal Kushilevitz, and Vinod Vaikuntanathan

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is collision resistant hash functions (CRH), which prevent an efficient attacker from finding a pair of inputs on which the function has the same output.
Cite as

Benny Applebaum, Naama Haramaty-Krasne, Yuval Ishai, Eyal Kushilevitz, and Vinod Vaikuntanathan. Low-Complexity Cryptographic Hash Functions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 7:1-7:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{applebaum_et_al:LIPIcs.ITCS.2017.7,
  author =	{Applebaum, Benny and Haramaty-Krasne, Naama and Ishai, Yuval and Kushilevitz, Eyal and Vaikuntanathan, Vinod},
  title =	{{Low-Complexity Cryptographic Hash Functions}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{7:1--7:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.7},
  URN =		{urn:nbn:de:0030-drops-81901},
  doi =		{10.4230/LIPIcs.ITCS.2017.7},
  annote =	{Keywords: Cryptography, hash functions, complexity theory, coding theory}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.26
Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity

Authors: Itay Hazan and Eyal Kushilevitz

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Direct-sum questions in (two-party) communication complexity ask whether two parties, Alice and Bob, can compute the value of a function f on l inputs (x_1,y_1),...,(x_l,y_l) more efficiently than by applying the best protocol for f, independently on each input (x_i,y_i). In spite of significant efforts to understand these questions (under various communication-complexity measures), the general question is still far from being well understood. In this paper, we offer a multiparty view of these questions: The direct-sum setting is just a two-player system with Alice having inputs x_1,...,x_l, Bob having inputs y_1,...,y_l and the desired output is f(x_1,y_1),...,f(x_l,y_l). The naive solution of solving the l problems independently, is modeled by a network with l (disconnected) pairs of players Alice i and Bob i, with inputs x_i,y_i respectively, and communication only within each pair. Then, we consider an intermediate ("star") model, where there is one Alice having l inputs x_1,...,x_l and l players Bob_1,...,Bob_l holding y_1,...,y_l, respectively (in fact, we consider few variants of this intermediate model, depending on whether communication between each Bob i and Alice is point-to-point or whether we allow broadcast). Our goal is to get a better understanding of the relation between the two extreme models (i.e., of the two-party direct-sum question). If, for instance, Alice and Bob can do better (for some complexity measure) than solving the l problems independently, we wish to understand what intermediate model already allows to do so (hereby understanding the "source" of such savings). If, on the other hand, we wish to prove that there is no better solution than solving the l problems independently, then our approach gives a way of breaking the task of proving such a statement into few (hopefully, easier) steps. We present several results of both types. Namely, for certain complexity measures, communication problems f and certain pairs of models, we can show gaps between the complexity of solving f on l instances in the two models in question; while, for certain other complexity measures and pairs of models, we can show that such gaps do not exist (for any communication problem f). For example, we prove that if only point-to-point communication is allowed in the intermediate "star" model, then significant savings are impossible in the public-coin randomized setting. On the other hand, in the private-coin randomized setting, if Alice is allowed to broadcast messages to all Bobs in the "star" network, then some savings are possible. While this approach does not lead yet to new results on the original two-party direct-sum question, we believe that our work gives new insights on the already-known direct-sum results, and may potentially lead to more such results in the future.
Cite as

Itay Hazan and Eyal Kushilevitz. Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hazan_et_al:LIPIcs.DISC.2017.26,
  author =	{Hazan, Itay and Kushilevitz, Eyal},
  title =	{{Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.26},
  URN =		{urn:nbn:de:0030-drops-79998},
  doi =		{10.4230/LIPIcs.DISC.2017.26},
  annote =	{Keywords: Communication Complexity, Direct Sum, Multiparty Communication}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.160
Lossy Chains and Fractional Secret Sharing

Authors: Yuval Ishai, Eyal Kushilevitz, and Omer Strulovich

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
Motivated by the goal of controlling the amount of work required to access a shared resource or to solve a cryptographic puzzle, we introduce and study the related notions of lossy chains and fractional secret sharing. Fractional secret sharing generalizes traditional secret sharing by allowing a fine-grained control over the amount of uncertainty about the secret. More concretely, a fractional secret sharing scheme realizes a fractional access structure f : 2^{[n]} -> {0,...,m-1} by guaranteeing that from the point of view of each set T \subseteq [n] of parties, the secret is uniformly distributed over a set of f(T) + 1 potential secrets. We show that every (monotone) fractional access structure can be realized. For symmetric structures, in which f(T) depends only on the size of T, we give an efficient construction with share size poly(n,log m). Our construction of fractional secret sharing schemes is based on the new notion of lossy chains which may be of independent interest. A lossy chain is a Markov chain (X_0,...,X_n) which starts with a random secret X_0 and gradually loses information about it at a rate which is specified by a loss function g. Concretely, in every step t, the distribution of X_0 conditioned on the value of X_t should always be uniformly distributed over a set of size g(t). We show how to construct such lossy chains efficiently for any possible loss function g, and prove that our construction achieves an optimal asymptotic information rate.
Cite as

Yuval Ishai, Eyal Kushilevitz, and Omer Strulovich. Lossy Chains and Fractional Secret Sharing. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 160-171, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{ishai_et_al:LIPIcs.STACS.2013.160,
  author =	{Ishai, Yuval and Kushilevitz, Eyal and Strulovich, Omer},
  title =	{{Lossy Chains and Fractional Secret Sharing}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{160--171},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.160},
  URN =		{urn:nbn:de:0030-drops-39319},
  doi =		{10.4230/LIPIcs.STACS.2013.160},
  annote =	{Keywords: Cryptography, secret sharing, Markov chains}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact